package 剑指offer;

public class 剑指Offer46把数字翻译成字符串 {
    public static void main(String[] args) {

        int num = 506;
//        System.out.println(translateNum(num));
        System.out.println(translateNum1(num));
    }


    public static int translateNum1(int num) {
        String str = String.valueOf(num);
        int N = str.length();
        int[] dp = new int[N+1];
        dp[N] = 1;
        for (int i = N-1;i >= 0;i--){
            int ways = dp[i+1];
            if (i+1 < N && (str.charAt(i) - '0') * 10 + (str.charAt(i+1) - '0') < 26 ){
                ways += dp[i+2];
            }
            dp[i] = ways;
        }
        return dp[0];
    }

    /**
     * 传入一个整数，就可以转换成对应得26个引文字母
     * @param num 数字
     * @return 返回共有多少种转换得结果
     */
    public static int translateNum(int num) {
        //递归
        if(num < 10){
            return 1;
        }
        //否则至少存在两位数
        //num，10：表示选择当前一位，num，20表示选择当前两位
        int p1 = translateNum(num / 10);
        int p2 = 0;
        if(10 <= num % 100  && num % 100 < 26){
            p2 = translateNum(num / 100);
        }

        return p1 + p2;
    }



}
